package com.str.BT;
public class BST {

// Inner class
  private static class BSTNode {
    Comparable data;
    BSTNode left;
    BSTNode right;

    BSTNode() {}
    BSTNode(Comparable obj) { data = obj; }
    BSTNode(Comparable obj, BSTNode leftChild, BSTNode rightChild) {
      data = obj; 
      left = leftChild; 
      right = rightChild;
    }

    public String toString()
    { return data.toString(); }
  }

  // Each BST Object is (a header of) a binary search tree (BST).
  // This BST is represented simply by a reference to its root node (root).
  private BSTNode root;      //root node of the tree
  private int count;
     
// Constructor
  public BST() 
  { clear(); }
  
// Modifiers
  public final void clear() {
   	root = null;
  	count = 0;
  }
 
  public void insert(Comparable val) 
  { root = insert(root, val); }
    
  public void delete(Comparable val) 
  { root = delete(root, val); }
    
// Accessors
  public boolean isEmpty()
  { return root == null; }

  public int size()
  { return count; }
  
  public boolean contains(Comparable val) 
  {	return search(root, val) != null; }

  public String toString()  
  { return toString(root, 0); }

// Auxiliary methods
  private BSTNode insert(BSTNode ref, Comparable val) {
  // Insert the element elem in this BST.
    if (ref == null) {
      count++; 
      return new BSTNode(val);
    }
    else {
      int comp = val.compareTo(ref.data);
      if (comp < 0)
        ref.left = insert(ref.left, val);
      else  // comp >= 0
        ref.right = insert(ref.right, val);
      return ref;  	   	
    }
  }

  private BSTNode delete(BSTNode ref, Comparable val) {
  // Delete the element elem in this BST. 
    if (ref != null) {
      int comp = val.compareTo(ref.data);
      if (comp == 0) {
        count--;
        return deleteTopmost(ref);
      }
      else if (comp < 0)
        ref.left = delete(ref.left, val);
      else  // comp > 0
        ref.right = delete(ref.right, val);
    }
    return ref;
  }
    
  private BSTNode deleteTopmost(BSTNode ref) {
    if (ref.left == null)
      return ref.right;
    else if (ref.right == null)
      return ref.left;
    else {  // this node has both a left child and a right child
      ref.data = getLeftmost(ref.right);
      ref.right = deleteLeftmost(ref.right);
      return ref;
    }
  }
  
  private Comparable getLeftmost(BSTNode ref) {
  // Return the element in the leftmost node of the (nonempty) subtree
  // whose topmost node is this.
    if (ref.left == null)  
      return ref.data;
    else return getLeftmost(ref.left);
  }
    
  private BSTNode deleteLeftmost(BSTNode ref) {
  // Delete the leftmost node of the (nonempty) subtree
  // whose topmost node is this.
  // Return a link to the modified subtree.
    if (ref.left == null) return ref.right;
    else {
      ref.left = deleteLeftmost(ref.left);
      return ref;
    }
  }
    
  private BSTNode search(BSTNode ref, Comparable val) {
    if (ref == null) return null; 
    else {      
      int comp = val.compareTo(ref.data);
      if (comp == 0)
        return ref;
      else if (comp < 0)
        return search(ref.left, val);
      else
        return search(ref.right, val);
    }
  }

  private String toString(BSTNode ref, int level) {
  	String buf = "";
    if (ref != null) {
      buf += toString(ref.right, level+1);
      for (int i=0; i<level; i++)
        buf += "    ";
      buf += ref.data + "\n";
      buf += toString(ref.left, level+1);
    }
    return buf;
  }
}
